package com.fanshuai.algorithms.datastructure.tree.binarytree;

import com.fanshuai.queue.LinkedQueue;
import com.fanshuai.queue.Queue;
import com.fanshuai.tree.Visitor;
import org.apache.commons.collections.CollectionUtils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BinaryTree {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public Node root;
    public BinaryTree() {
        root = null;
    }

    /**
     * 中序遍历
     * @param node
     * @param visitor
     */
    public static void inOrder(Node node, Visitor visitor) {
        if (null == node) {
            return;
        }

        inOrder(node.left, visitor);
        visitor.visit(node.value);
        inOrder(node.right, visitor);
    }

    /**
     * 广度优先遍历
     * @param node
     * @param visitor
     */
    public static void BFS(Node node, Visitor visitor) {
        Queue<Node> queue = new LinkedQueue<>();
        queue.enqueue(node);

        while (!queue.isEmpty()) {
            Node node1 = queue.dequeue();
            visitor.visit(node1.value);

            if (node1.left != null) {
                queue.enqueue(node1.left);
            }
            if (node1.right != null) {
                queue.enqueue(node1.right);
            }
        }
    }

    /**
     * 查找节点  非二叉排序树，所以需要递归左右子树
     * @param root
     * @param value
     * @return
     */
    public static Node findNode(Node root, int value) {
        if (null == root) {
            return null;
        }
        if (root.value == value) {
            return root;
        }

        Node node = findNode(root.left, value);
        if (null != node) {
            return node;
        }
        node = findNode(root.right, value);
        return node;
    }

    /**
     * 根据前序遍历和中序遍历结果，构建二叉树
     * @return
     */
    public static Node buildTree(int[] pre, int[] in) {
        if (pre.length != in.length || pre.length == 0) {
            return null;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }

        /**
         * 获取前序遍历在中序遍历中的索引
         */
        Map<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < pre.length; i++) {
            int index = map.get(pre[i]);
            inMap.put(pre[i], index);
        }

        return buildTree(pre, 0, pre.length - 1, in, 0, in.length - 1, inMap);
    }

    private static Node buildTree(int[] pre, int preStart, int preEnd,
                                  int[] in, int inStart, int inEnd, Map<Integer, Integer> inMap) {
        if (preStart < 0 || preEnd >= pre.length) {
            return null;
        }
        if (preEnd < preStart || inEnd < inStart) {
            return null;
        }

        Node root = new Node(pre[preStart]);

        int rootIndex = inMap.get(pre[preStart]);
        int leftTreeCount = rootIndex - inStart;

        root.left = buildTree(pre, preStart + 1, preStart + leftTreeCount, in, inStart, rootIndex - 1, inMap);
        root.right = buildTree(pre, preStart + leftTreeCount + 1, preEnd, in, rootIndex + 1, inEnd, inMap);
        return root;
    }

    /**
     * 根据广度优先遍历结果，构建二叉树. 输入为完全二叉树序列，空节点元素为null
     * @return
     */
    public static Node buildTreeFromBFS(Integer[] arr) {
        return buildTreeFromBFS(arr, 0);
    }

    private static Node buildTreeFromBFS(Integer[] arr, int index) {
        if (index >= arr.length) {
            return null;
        }
        if (arr[index] == null) {
            return null;
        }

        Node root = new Node(arr[index]);
        root.left = buildTreeFromBFS(arr, 2 * index + 1);
        root.right = buildTreeFromBFS(arr, 2 * index + 2);

        return root;
    }

    /**
     * 获取从根节点到叶节点的最大路径和  递归实现
     * @param root
     * @return
     */
    public static int getMaxPath1(Node root) {
        if (null == root) {
            return 0;
        }

        int left = getMaxPath1(root.left);
        int right = getMaxPath1(root.right);

        return root.value + Math.max(left, right);
    }

    /**
     * 获取从根节点到叶节点的最大路径和  回溯法实现
     * @param root
     * @return
     */
    public static int getMaxPath2(Node root) {
        IntValue intValue = new IntValue(Integer.MIN_VALUE);
        getMaxPath2(root, intValue, 0);
        return intValue.value;
    }

    private static void getMaxPath2(Node node, IntValue max, int sum) {
        if (node == null) {
            if (sum > max.value) {
                max.value = sum;
            }
            return;
        }

        getMaxPath2(node.left, max, sum + node.value);
        getMaxPath2(node.right, max, sum + node.value);
    }

    /**
     * 获取从根节点到叶节点的最大路径和, 返回路径  回溯法实现
     * @param root
     * @return
     */
    public static List<Integer> getMaxPath3(Node root) {
        IntListValue intListValue = new IntListValue();
        getMaxPath3(root, intListValue, new ArrayList<>());
        return intListValue.listValue;
    }

    private static void getMaxPath3(Node node, IntListValue maxPath, List<Integer> path) {
        if (node == null) {
            if (sum(path) > sum(maxPath.listValue)) {
                System.out.println("set max path to " + path);
                maxPath.listValue = new ArrayList<>(path);
            }
            return;
        }

        path.add(node.value);
        getMaxPath3(node.left, maxPath, path);
        getMaxPath3(node.right, maxPath, path);
        path.remove(path.size() - 1);
    }



    private static int sum(List<Integer> path) {
        if (CollectionUtils.isEmpty(path)) {
            return 0;
        }

        int sum = 0;
        for (int i = 0; i < path.size(); i++) {
            sum += path.get(i);
        }
        return sum;
    }

    /**
     * 求二叉树多个节点的公共祖先
     * @param root
     * @param nodes
     * @return
     */
    public static Node commonAncestor(Node root, Node[] nodes) {
        CommonNodeValue commonNodeValue = new CommonNodeValue();
        commonAncestor0(root, nodes, commonNodeValue);
        return commonNodeValue.node;
    }

    /**
     * 求二叉树多个节点的公共祖先  回溯法实现
     * @param node
     * @param nodes
     * @return  返回公共节点数量n
     */
    private static int commonAncestor0(Node node, Node[] nodes, CommonNodeValue commonNodeValue) {
        if (node == null) {
            return 0;
        }

        int hit = 0;
        for (int i = 0; i < nodes.length; i++) {
            if (node == nodes[i]) {
                hit = 1;
                break;
            }
        }

        int leftHit = commonAncestor0(node.left, nodes, commonNodeValue);
        int rightHit = commonAncestor0(node.right, nodes, commonNodeValue);
        int totalHit = hit + leftHit + rightHit;

        //当扫描的节点等于nodes数组节点数量时，说明已找到公共节点，赋值。公共节点只赋值一次
        if (totalHit == nodes.length && commonNodeValue.node == null) {
            commonNodeValue.node = node;
        }

        return totalHit;
    }

    /**
     * 判断二叉树相同
     * @param root1
     * @param root2
     * @return
     */
    public static boolean isSame(Node root1, Node root2) {
        if (null == root1 && null == root2) {
            return true;
        } else {
            if (null == root1) {
                return false;
            }
            if (null == root2) {
                return false;
            }

            boolean b = root1.value == root2.value;
            boolean left = isSame(root1.left, root2.left);
            boolean right = isSame(root1.right, root2.right);
            return b && left && right;
        }
    }

    /**
     * 全部节点加value
     * @param root
     * @param value
     */
    public static void plusValue(Node root, int value) {
        if (null == root) {
            return;
        }

        root.value += value;
        plusValue(root.left, value);
        plusValue(root.right, value);
    }

    /**
     * 是否为合法的二叉搜索树
     * 二叉搜索树：
     * 每个节点的值，小于左子树，小于右子树
     * @param root
     * @return
     */
    public static boolean isValidBST(Node root) {
        return isValidBST0(root, null, null);
    }

    private static boolean isValidBST0(Node node, Node min, Node max) {
        if (null == node) {
            return true;
        }

        if (min != null) {
            if (node.value <= min.value) {
                return false;
            }
        }
        if (max != null) {
            if (node.value >= max.value) {
                return false;
            }
        }

        return isValidBST0(node.left, min, node) && isValidBST0(node.right, node, max);
    }

    /**
     * 给一课二叉树，和一个目标值，节点上的值有正有负，返回树中和等于目标值的路径条数，让你编写 pathSum 函数
     * root = [10,5,-3,3,2,null,11,3,-2,null,1],
     sum = 8

     Return 3. The paths that sum to 8 are:

     1.  5 -> 3
     2.  5 -> 2 -> 1
     3. -3 -> 11

     递归实现
     * @param node
     * @param sum
     * @return
     */
    public static int pathSum(Node node, int sum) {
        if (null == node) {
            return 0;
        }

        return countSum(node, sum) + pathSum(node.left, sum) + pathSum(node.right, sum);
    }

    /**
     * 返回以node为根节点，路径和等于sum的路径条数
     * @param node
     * @param sum
     * @return
     */
    private static int countSum(Node node, int sum) {
        if (null == node) {
            return 0;
        }

        int cur = sum == node.value ? 1 : 0;
        int left = countSum(node.left, sum - node.value);
        int right = countSum(node.right, sum - node.value);
        return cur + left + right;
    }

    /**
     * 给一课二叉树，和一个目标值，节点上的值有正有负，返回树中和等于目标值的全部路径，每一条路径用list表示
     * 回溯法实现
     * @param node
     * @param sum
     * @return
     */
    public static List<List<Integer>> pathSum2(Node node, int sum) {
        List<List<Integer>> all = new ArrayList<>();
        pathSum2(node, sum, new ArrayList<>(), all);

        return all;
    }

    private static void pathSum2(Node node, int sum, List<Integer> path, List<List<Integer>> allPath) {
        if (null == node) {
            return;
        }

        countSum2(node, sum, path, allPath);
        pathSum2(node.left, sum, path, allPath);
        pathSum2(node.right, sum, path, allPath);
    }

    private static void countSum2(Node node, int sum, List<Integer> path, List<List<Integer>> allPath) {
        //递归出口
        if (null == node) {
            return;
        }

        path.add(node.value);
        //非递归出口，判断是否满足条件
        if (sum(path) == sum) {
            allPath.add(new ArrayList<>(path));
        }

        countSum2(node.left, sum, path, allPath);
        countSum2(node.right, sum, path, allPath);
        path.remove(path.size() - 1);
    }


}
